package leetcode.每日一题;

import leetcode.剑指offer.pojo.ListNode;
import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/1/16 12:56
 * @description：https://leetcode-cn.com/problems/linked-list-random-node/
 */
public class 链表随机节点 {
    @Test
    public void test() {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3)));
        Solution solution = new Solution(head);
        while (true) {
            System.out.println(solution.getRandom());
        }
    }

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    /*class Solution {
        private List<Integer> list;
        private Random random;
        public Solution(ListNode head) {
            list = new ArrayList<>();
            ListNode tmp = head;
            while (tmp != null) {
                list.add(tmp.val);
                tmp = tmp.next;
            }
            random = new Random();
        }

        public int getRandom() {
            return list.get(random.nextInt(list.size()));
        }
    }*/

    class Solution {
        private Random random;
        private ListNode head;
        public Solution(ListNode head) {
            this.head = head;
            random = new Random();
        }

        public int getRandom() {
            int i = 1;
            int ans = 0;
            ListNode tmp = head;
            while (tmp != null) {
                if (random.nextInt(i) == 0) {
                    ans = tmp.val;
                }
                tmp = tmp.next;
                i++;
            }
            return ans;
        }
    }

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

}
